---
title: "质数拆分"
created: 2025-11-28
tags:
  - 算法
---

# 质数拆分

## 题目 [质数拆分](https://www.lanqiao.cn/paper/3845/problem/809/)

![[image-a50f469d.png]]

## 思路分析

![[image-32a30deb.png]]

注意不是只拆成a+b 若a中还能拆出c和d要继续去拆

最开始写成了 拆分成ab俩 但是发现只有2，2017这一对

尝试对这一对进行dfs

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N = 100010;
bool isnot_prime[N];
set<int> primes;
int cnt = 0;

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isnot_prime[i]) {
            primes.insert(i);
            for (int j = i * 2; j <= n; j += i) {
                isnot_prime[j] = true;
            }
        }
    }
}

void dfs(set<int>::iterator it, set<int>::iterator end, int a, int b) {
    if (a == 0 && b == 0) {
        cnt++;
        return;
    }
    for (auto i = it; i != end; i++) {
        int x = *i;
        if (a >= x) dfs(next(i), end, a - x, b);
        if (b >= x) dfs(next(i), end, a, b - x);
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    get_primes(2019);

    dfs(primes.begin(), primes.end(), 2, 2017);

    cout << cnt / 2 << endl;
    return 0;
}
```

- 用一个从当前质数开始的迭代器，递归时只考虑这个迭代器之后的质数，以避免重复。
- 通过 **next(i)** 确保在递归时不会重复考虑相同的质数组合。
- 终止条件是当 **a** 和 **b** 同时为0时，这意味着找到了一种有效的组合方式。
- 由于每种组合可能会被计算两次（对于a和b的顺序），结果需要除以2。

在 C++ 中，使用 **next(i)** 是一种从给定迭代器（这里是 **i**）开始，向前移动一位的操作。这个函数属于 **<iterator>** 库，它返回一个新的迭代器，该迭代器指向当前迭代器的下一个元素。在 **set** 和其他容器的迭代器中使用 **next** 非常常见，尤其是当你需要处理迭代器但又不想改变原有迭代器的位置时。

在您的 **dfs** 函数中，使用 **next(i)** 有两个主要目的：

1. **避免重复组合**：通过从当前质数的下一个开始递归调用 **dfs**，确保每次递归考虑的质数集合都是减少的。这意味着对于每个质数，我们只考虑它之后的质数组合，从而避免了重复计算相同的组合。例如，如果质数集合是 **{2, 3, 5, 7}**，在考虑 **2** 时，接下来只考虑 **{3, 5, 7}** 而不再重新考虑 **2**。
2. **防止无限递归**：如果不使用 **next(i)**，则递归调用可能会不断重复相同的迭代器位置，导致无限递归。例如，如果我们继续用相同的 **i** 调用 **dfs**，则 **dfs** 函数可能会不停地尝试将同一个数 **x** 从 **a** 或 **b** 中减去，从而永远不会到达终止条件（**a == 0 && b == 0**）。

这里是具体的代码片段解释，展示了 **next(i)** 如何工作：

`for (auto i = it; i != end; i++) {`

`int x = *i;`

`if (a >= x) dfs(next(i), end, a - x, b); // 只考虑当前质数之后的质数来减少a`

`if (b >= x) dfs(next(i), end, a, b - x); // 只考虑当前质数之后的质数来减少b`

`}`

这样，每次递归调用都是从质数集合的一个更小的子集开始，减少计算量，避免重复，并尝试所有可能的组合。

但是效率太低了 运行结果半天出不来

考虑换dp写

发现其实是背包问题

从前i个数里面选 总价值恰好等于2019的所有选法的集合 属性count

状态：f[i][j]表示选到第i个数且当前体积是j的方案数

转移方程：

`f[i][j]+=f[i-1][j]不选第i个数`

`if(j>=prime[i])`

`f[i][j]+=f[i-1][j-prime[i]]选第i个数`

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
const int N=10010;
bool st[N];
int primes[N],cnt=1;
LL f[N][N];

void get_primes(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]){
			primes[cnt++]=i;
			for(int j=i;j<=n;j+=i)
				st[j]=true;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	get_primes(2019);
	int n=cnt-1,m=2019;
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			f[i][j]+=f[i-1][j];
			if(j>=primes[i])
				f[i][j]+=f[i-1][j-primes[i]];
		}
	}
	cout<<f[n][m];
	return 0;
}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long LL;

const int N=10010;

bool st[N];

int primes[N],cnt=1;

LL f[N];

void get_primes(int n){

	for(int i=2;i<=n;i++){

		if(!st[i]){

			primes[cnt++]=i;

			for(int j=i;j<=n;j+=i)

				st[j]=true;

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	get_primes(2019);

	int n=cnt-1,m=2019;

	f[0]=1;

	for(int i=1;i<=n;i++){

		for(int j=m;j>=primes[i];j--){

			f[j]=f[j]+f[j-primes[i]];

		}

	}

	cout<<f[m];

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[平方序列|平方序列]] 🏠 [[00-冲刺国赛]] ➡️ [[拼接|拼接]]